#include <iostream>
using namespace std;

//表结点（表示图的边）
class arcnode
{
public:
    arcnode(int adjvex):adjvex(adjvex){}
    ~arcnode(){delete nextarc;}
    int wt; //权重
    int adjvex; //顶点下标
    arcnode *nextarc=nullptr; //指针指向下一条边
};

//表头结点（表示图的顶点）
class vnode
{
public:
    vnode(char data):data(data){}
    ~vnode(){delete firstarc;}
    char data; //顶点数据，这里用字符表示
    arcnode *firstarc=nullptr; //指针指向第一条边（每条边只用一次，持有所有权）
    void addarc(int arc[],int size)
    {
        firstarc=new arcnode(arc[0]);
        if(size==1)
            return;
        arcnode** nowarcnode=&firstarc->nextarc;
        for(int i=1;i<size;i++)
        {
            *nowarcnode=new arcnode(arc[i]);
            nowarcnode=&((*nowarcnode)->nextarc);
        }
    }
};

class search
{
public:
    vnode *g;
    search(vnode g[]):g(g){}

    void dfs(vnode &vn)
    {
        cout<<vn.data<<endl;
        dfs(vn.firstarc);
    }

    void dfs(arcnode* an)
    {
        if(an==nullptr)
            return;
        else
        {
            vnode nextvn=g[an->adjvex];
            cout<<nextvn.data<<endl; //输出当前这条边连接到的节点的值
            if(nextvn.firstarc!=nullptr) //如果该节点有边，先往下层走（深度优先）
                dfs(nextvn);
            else //该节点没有边了，就往之前那个节点没遍历的边走
                dfs(an->nextarc);
        }
    }

    void bfs(vnode &vn)
    {
        cout<<vn.data<<endl;
        bfs(vn.firstarc);
    }

    void bfs(arcnode* an)
    {
        if(an==nullptr)
            return;
        else
        {
            vnode nextvn=g[an->adjvex];
            cout<<nextvn.data<<endl; //输出当前这条边连接到的节点的值
            bfs(an->nextarc); //先遍历同一个节点的边
            if(nextvn.firstarc!=nullptr) //同一个节点的边都遍历完了，遍历边连接的节点的
                bfs(nextvn);
        }
    }
};

int main()
{
    vnode vexs[5]={vnode('A'),vnode('B'),vnode('C'),vnode('D'),vnode('E')}; //图
    int arr[]={1,3,4};
    vexs[0].addarc(arr,3);
    arr[0]=0;arr[1]=2;
    vexs[1].addarc(arr,2);
    arr[0]=1;arr[1]=3;
    vexs[2].addarc(arr,2);
    arr[0]=1;arr[1]=3;
    vexs[3].addarc(arr,2);
    arr[0]=0;arr[1]=2;arr[2]=4;
    vexs[4].addarc(arr,3);
    arr[0]=0;arr[1]=3;
    vexs[5].addarc(arr,2);
}
